/*
 * 0050. 数组剔除元素后的乘积
 * 给定一个整数数组A。
 * 定义B[i] = A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1]， 计算B的时候请不要使用除法。
 * 
 * 样例
 * 给出A=[1, 2, 3]，返回 B为[6, 3, 2]
 * 
 * 2018.10.09 @jeyming
 * https://www.lintcode.com/problem/product-of-array-exclude-itself/description
 */
package product_of_array_exclude_itself_0050;

import java.util.ArrayList;
import java.util.List;

public class Product_of_array_exclude_itself_0050 {
	/*
	 * @param nums: Given an integers array A
	 * 
	 * @return: A long long array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... *
	 * A[n-1]
	 */
	public List<Long> productExcludeItself(List<Integer> nums) {
		List<Long> list = new ArrayList<>();
		if (nums.size() == 0) {
			return list;
		}
		list.add(list.size(), (long) 1);
		for (int i = 0; i < nums.size() - 1; ++i) {
			list.add(list.size(), list.get(i) * nums.get(i));
		}
		int tmp = 1;
		for (int i = nums.size() - 1; i >= 0; --i) {
			list.add(i, list.get(i) * tmp);
			tmp *= nums.get(i);
		}
		return list;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
